home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Internet Tools 1993 July / Internet Tools.iso / RockRidge / ip / trace / tcpdump-2.2.1 / gencode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-22  |  23.5 KB  |  1,385 lines
  1. /*
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that: (1) source code distributions
  7.  * retain the above copyright notice and this paragraph in its entirety, (2)
  8.  * distributions including binary code include the above copyright notice and
  9.  * this paragraph in its entirety in the documentation or other materials
  10.  * provided with the distribution, and (3) all advertising materials mentioning
  11.  * features or use of this software display the following acknowledgement:
  12.  * ``This product includes software developed by the University of California,
  13.  * Lawrence Berkeley Laboratory and its contributors.'' Neither the name of
  14.  * the University nor the names of its contributors may be used to endorse
  15.  * or promote products derived from this software without specific prior
  16.  * written permission.
  17.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  18.  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  19.  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  20.  */
  21. #ifndef lint
  22. static char rcsid[] =
  23.     "@(#) $Header: gencode.c,v 1.33 92/05/22 16:38:39 mccanne Exp $ (LBL)";
  24. #endif
  25.  
  26. #ifdef __STDC__
  27. #include <stdlib.h>
  28. #endif
  29. #include <sys/types.h>
  30. #include <sys/socket.h>
  31. #include <net/if.h>
  32. #include <netinet/in.h>
  33. #include <netinet/if_ether.h>
  34.  
  35. #include <sys/time.h>
  36. #include <net/bpf.h>
  37.  
  38. #include "interface.h"
  39. #include "gencode.h"
  40. #include "nametoaddr.h"
  41. #include "extract.h"
  42.  
  43. #define JMP(c) ((c)|BPF_JMP|BPF_K)
  44.  
  45. extern struct bpf_insn *icode_to_fcode();
  46. extern u_long net_mask();
  47. static void init_linktype();
  48.  
  49. static int alloc_reg();
  50. static void free_reg();
  51.  
  52. static struct block *root;
  53.  
  54. /*
  55.  * We divy out chunks of memory rather than call malloc each time so
  56.  * we don't have to worry about leaking memory.  It's probably
  57.  * not a big deal if all this memory was wasted but it this ever
  58.  * goes into a library that would probably not be a good idea.
  59.  */
  60. #define NCHUNKS 16
  61. #define CHUNK0SIZE 1024
  62. struct chunk {
  63.     u_int n_left;
  64.     void *m;
  65. };
  66.  
  67. static struct chunk chunks[NCHUNKS];
  68. static int cur_chunk;
  69.  
  70. static void *
  71. newchunk(n)
  72.     u_int n;
  73. {
  74.     struct chunk *cp;
  75.     int k, size;
  76.     
  77.     /* XXX Round up to nearest long. */
  78.     n = (n + sizeof(long) - 1) & ~(sizeof(long) - 1);
  79.  
  80.     cp = &chunks[cur_chunk];
  81.     if (n > cp->n_left) {
  82.         ++cp, k = ++cur_chunk;
  83.         if (k >= NCHUNKS)
  84.             error("out of memory");
  85.         size = CHUNK0SIZE << k;
  86.         cp->m = (void *)malloc(size);
  87.         bzero((char *)cp->m, size);
  88.         cp->n_left = size;
  89.         if (n > size)
  90.             error("out of memory");
  91.     }
  92.     cp->n_left -= n;
  93.     return (void *)((char *)cp->m + cp->n_left);
  94. }
  95.  
  96. static void
  97. freechunks()
  98. {
  99.     int i;
  100.  
  101.     for (i = 0; i < NCHUNKS; ++i)
  102.         if (chunks[i].m)
  103.             free(chunks[i].m);
  104. }
  105.  
  106. static inline struct block *
  107. new_block(code)
  108.     int code;
  109. {
  110.     struct block *p;
  111.  
  112.     p = (struct block *)newchunk(sizeof(*p));
  113.     p->s.code = code;
  114.     p->head = p;
  115.  
  116.     return p;
  117. }
  118.  
  119. static inline struct slist *
  120. new_stmt(code)
  121.     int code;
  122. {
  123.     struct slist *p;
  124.  
  125.     p = (struct slist *)newchunk(sizeof(*p));
  126.     p->s.code = code;
  127.  
  128.     return p;
  129. }
  130.  
  131. static struct block *
  132. gen_retblk(v)
  133.     int v;
  134. {
  135.     struct block *b = new_block(BPF_RET|BPF_K);
  136.  
  137.     b->s.k = v;
  138.     return b;
  139. }
  140.  
  141. static inline void
  142. syntax()
  143. {
  144.     error("syntax error in filter expression");
  145. }
  146.  
  147. static u_long netmask;
  148.  
  149. struct bpf_program *
  150. parse(buf, Oflag, linktype, mask)
  151.     char *buf;
  152.     int Oflag;
  153.     int linktype;
  154.     u_long mask;
  155. {
  156.     extern int n_errors;
  157.     static struct bpf_program F;
  158.     struct bpf_insn *p;
  159.     int len;
  160.  
  161.     netmask = mask;
  162.  
  163.     F.bf_insns = 0;
  164.     F.bf_len = 0;
  165.  
  166.     lex_init(buf ? buf : "");
  167.     init_linktype(linktype);
  168.     yyparse();
  169.  
  170.     if (n_errors)
  171.         syntax();
  172.  
  173.     if (root == 0)
  174.         root = gen_retblk(snaplen);
  175.  
  176.     if (Oflag) {
  177.         optimize(&root);
  178.         if (root == 0 || 
  179.             (root->s.code == (BPF_RET|BPF_K) && root->s.k == 0))
  180.             error("expression rejects all packets");
  181.     }
  182.     p = icode_to_fcode(root, &len);
  183.     F.bf_insns = p;
  184.     F.bf_len  = len;
  185.  
  186.     freechunks();
  187.     return &F;
  188. }
  189.  
  190. /*
  191.  * Backpatch the blocks in 'list' to 'target'.  The 'sense' field indicates
  192.  * which of the jt and jf fields has been resolved and which is a pointer
  193.  * back to another unresolved block (or nil).  At least one of the fields
  194.  * in each block is already resolved.
  195.  */
  196. static void
  197. backpatch(list, target)
  198.     struct block *list, *target;
  199. {
  200.     struct block *next;
  201.  
  202.     while (list) {
  203.         if (!list->sense) {
  204.             next = JT(list);
  205.             JT(list) = target;
  206.         } else {
  207.             next = JF(list);
  208.             JF(list) = target;
  209.         }
  210.         list = next;
  211.     }
  212. }
  213.  
  214. /*
  215.  * Merge the lists in b0 and b1, using the 'sense' field to indicate
  216.  * which of jt and jf is the link.
  217.  */
  218. static void
  219. merge(b0, b1)
  220.     struct block *b0, *b1;
  221. {
  222.     register struct block **p = &b0;
  223.  
  224.     /* Find end of list. */
  225.     while (*p)
  226.         p = !((*p)->sense) ? &JT(*p) : &JF(*p);
  227.  
  228.     /* Concatenate the lists. */
  229.     *p = b1;
  230. }
  231.  
  232. void
  233. finish_parse(p)
  234.     struct block *p;
  235. {
  236.     backpatch(p, gen_retblk(snaplen));
  237.     p->sense = !p->sense;
  238.     backpatch(p, gen_retblk(0));
  239.     root = p->head;
  240. }
  241.  
  242. void
  243. gen_and(b0, b1)
  244.     struct block *b0, *b1;
  245. {
  246.     backpatch(b0, b1->head);
  247.     b0->sense = !b0->sense;
  248.     b1->sense = !b1->sense;
  249.     merge(b1, b0);
  250.     b1->sense = !b1->sense;
  251.     b1->head = b0->head;
  252. }
  253.  
  254. void
  255. gen_or(b0, b1)
  256.     struct block *b0, *b1;
  257. {
  258.     b0->sense = !b0->sense;
  259.     backpatch(b0, b1->head);
  260.     b0->sense = !b0->sense;
  261.     merge(b1, b0);
  262.     b1->head = b0->head;
  263. }
  264.  
  265. void
  266. gen_not(b)
  267.     struct block *b;
  268. {
  269.     b->sense = !b->sense;
  270. }
  271.  
  272. static struct block *
  273. gen_cmp(offset, size, v)
  274.     u_int offset, size;
  275.     long v;
  276. {
  277.     struct slist *s;
  278.     struct block *b;
  279.  
  280.     s = new_stmt(BPF_LD|BPF_ABS|size);
  281.     s->s.k = offset;
  282.  
  283.     b = new_block(JMP(BPF_JEQ));
  284.     b->stmts = s;
  285.     b->s.k = v;
  286.  
  287.     return b;
  288. }
  289.  
  290. struct block *
  291. gen_mcmp(offset, size, v, mask)
  292.     u_int offset, size;
  293.     long v;
  294.     u_long mask;
  295. {
  296.     struct block *b = gen_cmp(offset, size, v);
  297.     struct slist *s;
  298.  
  299.     if (mask != 0xffffffff) {
  300.         s = new_stmt(BPF_ALU|BPF_AND|BPF_K);
  301.         s->s.k = mask;
  302.         b->stmts->next = s;
  303.     }
  304.     return b;
  305. }
  306.  
  307. struct block *
  308. gen_bcmp(offset, size, v)
  309.     u_int offset;
  310.     u_int size;
  311.     u_char *v;
  312. {
  313.     struct block *b, *tmp;
  314.     int k;
  315.  
  316.     b = 0;
  317.     while (size >= 4) {
  318.         k = size - 4;
  319.         tmp = gen_cmp(offset + k, BPF_W, EXTRACT_LONG(&v[k]));
  320.         if (b != 0)
  321.             gen_and(b, tmp);
  322.         b = tmp;
  323.         size -= 4;
  324.     }
  325.     while (size >= 2) {
  326.         k = size - 2;
  327.         tmp = gen_cmp(offset + k, BPF_H, (long)EXTRACT_SHORT(&v[k]));
  328.         if (b != 0)
  329.             gen_and(b, tmp);
  330.         b = tmp;
  331.         size -= 2;
  332.     }
  333.     if (size > 0) {
  334.         tmp = gen_cmp(offset, BPF_B, (long)v[0]);
  335.         if (b != 0)
  336.             gen_and(b, tmp);
  337.         b = tmp;
  338.     }
  339.     return b;
  340. }
  341.  
  342. /*
  343.  * Various code contructs need to know the layout of the data link
  344.  * layer.  These variables give the necessary offsets.  off_linktype
  345.  * is set to -1 for no encapsulation, in which case, IP is assumed.
  346.  */
  347. static u_int off_linktype;
  348. static u_int off_nl;
  349. static int linktype;
  350.  
  351. static void
  352. init_linktype(type)
  353.     int type;
  354. {
  355.     linktype = type;
  356.  
  357.     switch (type) {
  358.  
  359.     case DLT_EN10MB:
  360.         off_linktype = 12;
  361.         off_nl = 14;
  362.         return;
  363.  
  364.     case DLT_SLIP:
  365.         /*
  366.          * SLIP doesn't have a link level type.  The 16 byte
  367.          * header is hacked into our SLIP driver.
  368.          */
  369.         off_linktype = -1;
  370.         off_nl = 16;
  371.         return;
  372.  
  373.     case DLT_NULL:
  374.         off_linktype = -1;
  375.         off_nl = 0;
  376.         return;
  377.  
  378.     case DLT_PPP:
  379.         off_linktype = 2;
  380.         off_nl = 4;
  381.         return;
  382.  
  383.     case DLT_FDDI:
  384.         off_linktype = 19;
  385.         off_nl = 21;
  386.         return;
  387.  
  388.     case DLT_IEEE802:
  389.         off_linktype = 20;
  390.         off_nl = 22;
  391.         return;
  392.     }
  393.     error("unknown data link type 0x%x", linktype);
  394.     /* NOTREACHED */
  395. }
  396.  
  397. static struct block *
  398. gen_uncond(rsense)
  399.     int rsense;
  400. {
  401.     struct block *b;
  402.     struct slist *s;
  403.  
  404.     s = new_stmt(BPF_LD|BPF_IMM);
  405.     s->s.k = !rsense;
  406.     b = new_block(JMP(BPF_JEQ));
  407.     b->stmts = s;
  408.  
  409.     return b;
  410. }
  411.  
  412. static inline struct block *
  413. gen_true()
  414. {
  415.     return gen_uncond(1);
  416. }
  417.  
  418. static inline struct block *
  419. gen_false()
  420. {
  421.     return gen_uncond(0);
  422. }
  423.  
  424. struct block *
  425. gen_linktype(proto)
  426.     int proto;
  427. {
  428.     switch (linktype) {
  429.     case DLT_SLIP:
  430.         if (proto == ETHERTYPE_IP)
  431.             return gen_true();
  432.         else
  433.             return gen_false();
  434.  
  435.     case DLT_PPP:
  436.         if (proto == ETHERTYPE_IP)
  437.             proto = 0x0021;        /* XXX - need ppp.h defs */
  438.         break;
  439.     }
  440.     return gen_cmp(off_linktype, BPF_H, (long)proto);
  441. }
  442.  
  443. static struct block *
  444. gen_hostop(addr, mask, dir, proto, src_off, dst_off)
  445.     u_long addr;
  446.     u_long mask;
  447.     int dir, proto;
  448.     u_int src_off, dst_off;
  449. {
  450.     struct block *b0, *b1;
  451.     u_int offset;
  452.  
  453.     switch (dir) {
  454.  
  455.     case Q_SRC:
  456.         offset = src_off;
  457.         break;
  458.  
  459.     case Q_DST:
  460.         offset = dst_off;
  461.         break;
  462.  
  463.     case Q_AND:
  464.         b0 = gen_hostop(addr, mask, Q_SRC, proto, src_off, dst_off);
  465.         b1 = gen_hostop(addr, mask, Q_DST, proto, src_off, dst_off);
  466.         gen_and(b0, b1);
  467.         return b1;
  468.  
  469.     case Q_OR:
  470.     case Q_DEFAULT:
  471.         b0 = gen_hostop(addr, mask, Q_SRC, proto, src_off, dst_off);
  472.         b1 = gen_hostop(addr, mask, Q_DST, proto, src_off, dst_off);
  473.         gen_or(b0, b1);
  474.         return b1;
  475.  
  476.     default:
  477.         abort();
  478.     }
  479.     b0 = gen_linktype(proto);
  480.     b1 = gen_mcmp(offset, BPF_W, (long)addr, mask);
  481.     gen_and(b0, b1);
  482.     return b1;
  483. }
  484.  
  485. static struct block *
  486. gen_ehostop(eaddr, dir)
  487.     u_char *eaddr;
  488.     int dir;
  489. {
  490.     struct block *b0, *b1;
  491.  
  492.     switch (dir) {
  493.     case Q_SRC:
  494.         return gen_bcmp(6, 6, eaddr);
  495.  
  496.     case Q_DST:
  497.         return gen_bcmp(0, 6, eaddr);
  498.  
  499.     case Q_AND:
  500.         b0 = gen_ehostop(eaddr, Q_SRC);
  501.         b1 = gen_ehostop(eaddr, Q_DST);
  502.         gen_and(b0, b1);
  503.         return b1;
  504.         
  505.     case Q_DEFAULT:
  506.     case Q_OR:
  507.         b0 = gen_ehostop(eaddr, Q_SRC);
  508.         b1 = gen_ehostop(eaddr, Q_DST);
  509.         gen_or(b0, b1);
  510.         return b1;
  511.     }
  512.     abort();
  513.     /* NOTREACHED */
  514. }
  515.  
  516. static struct block *
  517. gen_host(addr, mask, proto, dir)
  518.     u_long addr;
  519.     u_long mask;
  520.     int proto;
  521.     int dir;
  522. {
  523.     struct block *b0, *b1;
  524.  
  525.     switch (proto) {
  526.  
  527.     case Q_DEFAULT:
  528.         b0 = gen_host(addr, mask, Q_IP, dir);
  529.         b1 = gen_host(addr, mask, Q_ARP, dir);
  530.         gen_or(b0, b1);
  531.         b0 = gen_host(addr, mask, Q_RARP, dir);
  532.         gen_or(b1, b0);
  533.         return b0;
  534.  
  535.     case Q_IP:
  536.         return gen_hostop(addr, mask, dir, ETHERTYPE_IP, 
  537.                   off_nl + 12, off_nl + 16);
  538.  
  539.     case Q_RARP:
  540.         return gen_hostop(addr, mask, dir, ETHERTYPE_REVARP,
  541.                   off_nl + 14, off_nl + 24);
  542.  
  543.     case Q_ARP:
  544.         return gen_hostop(addr, mask, dir, ETHERTYPE_ARP,
  545.                   off_nl + 14, off_nl + 24);
  546.  
  547.     case Q_TCP:
  548.         error("'tcp' modifier applied to host");
  549.  
  550.     case Q_UDP:
  551.         error("'udp' modifier applied to host");
  552.  
  553.     case Q_ICMP:
  554.         error("'icmp' modifier applied to host");
  555.     }
  556.     abort();
  557.     /* NOTREACHED */
  558. }
  559.  
  560. static struct block *
  561. gen_gateway(eaddr, alist, proto, dir)
  562.     u_char *eaddr;
  563.     u_long **alist;
  564.     int proto;
  565.     int dir;
  566. {
  567.     struct block *b0, *b1, *tmp;
  568.  
  569.     if (dir != 0)
  570.         error("direction applied to 'gateway'");
  571.  
  572.     switch (proto) {
  573.     case Q_DEFAULT:
  574.     case Q_IP:
  575.     case Q_ARP:
  576.     case Q_RARP:
  577.         b0 = gen_ehostop(eaddr, Q_OR);
  578.         b1 = gen_host(**alist++, 0xffffffffL, proto, Q_OR);
  579.         while (*alist) {
  580.             tmp = gen_host(**alist++, 0xffffffffL, proto, Q_OR);
  581.             gen_or(b1, tmp);
  582.             b1 = tmp;
  583.         }
  584.         gen_not(b1);
  585.         gen_and(b0, b1);
  586.         return b1;
  587.     }
  588.     error("illegal modifier of 'gateway'");
  589.     /* NOTREACHED */
  590. }
  591.  
  592. struct block *
  593. gen_proto_abbrev(proto)
  594.     int proto;
  595. {
  596.     struct block *b0, *b1;
  597.  
  598.     switch (proto) {
  599.  
  600.     case Q_TCP:
  601.         b0 = gen_linktype(ETHERTYPE_IP);
  602.         b1 = gen_cmp(off_nl + 9, BPF_B, (long)IPPROTO_TCP);
  603.         gen_and(b0, b1);
  604.         break;
  605.         
  606.     case Q_UDP:
  607.         b0 =  gen_linktype(ETHERTYPE_IP);
  608.         b1 = gen_cmp(off_nl + 9, BPF_B, (long)IPPROTO_UDP);
  609.         gen_and(b0, b1);
  610.         break;
  611.  
  612.     case Q_ICMP:
  613.         b0 =  gen_linktype(ETHERTYPE_IP);
  614.         b1 = gen_cmp(off_nl + 9, BPF_B, (long)IPPROTO_ICMP);
  615.         gen_and(b0, b1);
  616.         break;
  617.  
  618.     case Q_IP:
  619.         b1 =  gen_linktype(ETHERTYPE_IP);
  620.         break;
  621.  
  622.     case Q_ARP:
  623.         b1 =  gen_linktype(ETHERTYPE_ARP);
  624.         break;
  625.  
  626.     case Q_RARP:
  627.         b1 =  gen_linktype(ETHERTYPE_REVARP);
  628.         break;
  629.  
  630.     case Q_LINK:
  631.         error("link layer applied in wrong context");
  632.  
  633.     default:
  634.         abort();
  635.     }
  636.     return b1;
  637. }
  638.  
  639. static struct block *
  640. gen_ipfrag()
  641. {
  642.     struct slist *s;
  643.     struct block *b;
  644.  
  645.     /* not ip frag */
  646.     s = new_stmt(BPF_LD|BPF_H|BPF_ABS);
  647.     s->s.k = off_nl + 6;
  648.     b = new_block(JMP(BPF_JSET));
  649.     b->s.k = 0x1fff;
  650.     b->stmts = s;
  651.     gen_not(b);
  652.  
  653.     return b;
  654. }
  655.  
  656. static struct block *
  657. gen_portatom(off, v)
  658.     int off;
  659.     long v;
  660. {
  661.     struct slist *s;
  662.     struct block *b;
  663.  
  664.     s = new_stmt(BPF_LDX|BPF_MSH|BPF_B);
  665.     s->s.k = off_nl;
  666.  
  667.     s->next = new_stmt(BPF_LD|BPF_IND|BPF_H);
  668.     s->next->s.k = off_nl + off;
  669.  
  670.     b = new_block(JMP(BPF_JEQ));
  671.     b->stmts = s;
  672.     b->s.k = v;
  673.  
  674.     return b;
  675. }
  676.  
  677. struct block *
  678. gen_portop(port, proto, dir)
  679.     int port;
  680.     int proto;
  681.     int dir;
  682. {
  683.     struct block *b0, *b1, *tmp;
  684.  
  685.     /* ip proto 'proto' */
  686.     tmp = gen_cmp(off_nl + 9, BPF_B, (long)proto);
  687.     b0 = gen_ipfrag();
  688.     gen_and(tmp, b0);
  689.  
  690.     switch (dir) {
  691.     case Q_SRC:
  692.         b1 = gen_portatom(0, (long)port);
  693.         break;
  694.  
  695.     case Q_DST:
  696.         b1 = gen_portatom(2, (long)port);
  697.         break;
  698.  
  699.     case Q_OR:
  700.     case Q_DEFAULT:
  701.         tmp = gen_portatom(0, (long)port);
  702.         b1 = gen_portatom(2, (long)port);
  703.         gen_or(tmp, b1);
  704.         break;
  705.  
  706.     case Q_AND:
  707.         tmp = gen_portatom(0, (long)port);
  708.         b1 = gen_portatom(2, (long)port);
  709.         gen_and(tmp, b1);
  710.         break;
  711.  
  712.     default:
  713.         abort();
  714.     }
  715.     gen_and(b0, b1);
  716.  
  717.     return b1;
  718. }
  719.  
  720. static struct block *
  721. gen_port(port, ip_proto, dir)
  722.     int port;
  723.     int ip_proto;
  724.     int dir;
  725. {
  726.     struct block *b0, *b1, *tmp;
  727.  
  728.     /* ether proto ip */
  729.     b0 =  gen_linktype(ETHERTYPE_IP);
  730.     
  731.     switch (ip_proto) {
  732.     case IPPROTO_UDP:
  733.     case IPPROTO_TCP:
  734.         b1 = gen_portop(port, ip_proto, dir);
  735.         break;
  736.  
  737.     case PROTO_UNDEF:
  738.         tmp = gen_portop(port, IPPROTO_TCP, dir);
  739.         b1 = gen_portop(port, IPPROTO_UDP, dir);
  740.         gen_or(tmp, b1);
  741.         break;
  742.  
  743.     default:
  744.         abort();
  745.     }
  746.     gen_and(b0, b1);
  747.     return b1;
  748. }
  749.  
  750. int
  751. lookup_proto(name, proto)
  752.     char *name;
  753.     int proto;
  754. {
  755.     int v;
  756.  
  757.     switch (proto) {
  758.     case Q_DEFAULT:
  759.     case Q_IP:
  760.         v = s_nametoproto(name);
  761.         if (v == PROTO_UNDEF)
  762.             error("unknown ip proto '%s'", name);
  763.         break;
  764.  
  765.     case Q_LINK:
  766.         /* XXX should look up h/w protocol type based on linktype */
  767.         v = s_nametoeproto(name);
  768.         if (v == PROTO_UNDEF)
  769.             error("unknown ether proto '%s'", name);
  770.         break;
  771.  
  772.     default:
  773.         v = PROTO_UNDEF;
  774.         break;
  775.     }
  776.     return v;
  777. }
  778.  
  779. struct block *
  780. gen_proto(v, proto, dir)
  781.     int v;
  782.     int proto;
  783.     int dir;
  784. {
  785.     struct block *b0, *b1;
  786.  
  787.     if (dir != Q_DEFAULT)
  788.         error("direction applied to 'proto'");
  789.     
  790.     switch (proto) {
  791.     case Q_DEFAULT:
  792.     case Q_IP:
  793.         b0 = gen_linktype(ETHERTYPE_IP);
  794.         b1 = gen_cmp(off_nl + 9, BPF_B, (long)v);
  795.         gen_and(b0, b1);
  796.         return b1;
  797.  
  798.     case Q_ARP:
  799.         error("arp does not encapsulate another protocol");
  800.         /* NOTREACHED */
  801.         
  802.     case Q_RARP:
  803.         error("rarp does not encapsulate another protocol");
  804.         /* NOTREACHED */
  805.  
  806.     case Q_LINK:
  807.         return gen_linktype(v);
  808.  
  809.     case Q_UDP:
  810.         error("'udp proto' is bogus");
  811.  
  812.     case Q_TCP:
  813.         error("'tcp proto' is bogus");
  814.  
  815.     case Q_ICMP:
  816.         error("'icmp proto' is bogus");
  817.     }
  818.     abort();
  819.     /* NOTREACHED */
  820. }
  821.     
  822. struct block *
  823. gen_scode(name, q)
  824.     char *name;
  825.     struct qual q;
  826. {
  827.     int proto = q.proto;
  828.     int dir = q.dir;
  829.     u_char *eaddr;
  830.     u_long mask, addr, **alist;
  831.     struct block *b, *tmp;
  832.     int port, real_proto;
  833.  
  834.     switch (q.addr) {
  835.  
  836.     case Q_NET:
  837.         addr = s_nametonetaddr(name);
  838.         if (addr == 0)
  839.             error("unknown network '%s'", name);
  840.         mask = net_mask(&addr);
  841.         return gen_host(addr, mask, proto, dir);
  842.  
  843.     case Q_DEFAULT:
  844.     case Q_HOST:
  845.         if (proto == Q_LINK) {
  846.             /* XXX Should lookup hw addr based on link layer */
  847.             eaddr = ETHER_hostton(name);
  848.             if (eaddr == 0)
  849.                 error("unknown ether host '%s'", name);
  850.             return gen_ehostop(eaddr, dir);
  851.  
  852.         } else {
  853.             alist = s_nametoaddr(name);
  854.             if (alist == 0 || *alist == 0)
  855.                 error("uknown host '%s'", name);
  856.             b = gen_host(**alist++, 0xffffffffL, proto, dir);
  857.             while (*alist) {
  858.                 tmp = gen_host(**alist++, 0xffffffffL, 
  859.                            proto, dir);
  860.                 gen_or(b, tmp);
  861.                 b = tmp;
  862.             }
  863.             return b;
  864.         }
  865.  
  866.     case Q_PORT: 
  867.         if (proto != Q_DEFAULT && proto != Q_UDP && proto != Q_TCP)
  868.             error("illegal qualifier of 'port'");
  869.         if (s_nametoport(name, &port, &real_proto) == 0)
  870.             error("unknown port '%s'", name);
  871.         if (proto == Q_UDP) {
  872.             if (real_proto == IPPROTO_TCP)
  873.                 error("port '%s' is tcp", name);
  874.             else
  875.                 /* override PROTO_UNDEF */
  876.                 real_proto = IPPROTO_UDP;
  877.         }
  878.         if (proto == Q_TCP) {
  879.             if (real_proto == IPPROTO_UDP)
  880.                 error("port '%s' is udp", name);
  881.             else
  882.                 /* override PROTO_UNDEF */
  883.                 real_proto = IPPROTO_TCP;
  884.         }
  885.         return gen_port(port, real_proto, dir);
  886.  
  887.     case Q_GATEWAY:
  888.         eaddr = ETHER_hostton(name);
  889.         if (eaddr == 0)
  890.             error("unknown ether host: %s", name);
  891.             
  892.         alist = s_nametoaddr(name);
  893.         if (alist == 0 || *alist == 0)
  894.             error("uknown host '%s'", name);
  895.         return gen_gateway(eaddr, alist, proto, dir);
  896.  
  897.     case Q_PROTO:
  898.         real_proto = lookup_proto(name, proto);
  899.         if (real_proto >= 0)
  900.             return gen_proto(real_proto, proto, dir);
  901.         else
  902.             error("unknown protocol: %s", name);
  903.  
  904.     case Q_UNDEF:
  905.         syntax();
  906.         /* NOTREACHED */
  907.     }
  908.     abort();
  909.     /* NOTREACHED */
  910. }
  911.  
  912. struct block *
  913. gen_ncode(v, q)
  914.     u_long v;
  915.     struct qual q;
  916. {
  917.     u_long mask;
  918.     int proto = q.proto;
  919.     int dir = q.dir;
  920.  
  921.     switch (q.addr) {
  922.  
  923.     case Q_DEFAULT:
  924.     case Q_HOST:
  925.     case Q_NET:
  926.         mask = net_mask(&v);
  927.         return gen_host(v, mask, proto, dir);
  928.  
  929.     case Q_PORT:
  930.         if (proto == Q_UDP)
  931.             proto = IPPROTO_UDP;
  932.         else if (proto == Q_TCP)
  933.             proto = IPPROTO_TCP;
  934.         else if (proto == Q_DEFAULT)
  935.             proto = PROTO_UNDEF;
  936.         else
  937.             error("illegal qualifier of 'port'");
  938.  
  939.         return gen_port((int)v, proto, dir);
  940.  
  941.     case Q_GATEWAY:
  942.         error("'gateway' requires a name");
  943.         /* NOTREACHED */
  944.  
  945.     case Q_PROTO:
  946.         return gen_proto((int)v, proto, dir);
  947.  
  948.     case Q_UNDEF:
  949.         syntax();
  950.         /* NOTREACHED */
  951.     }
  952.     abort();
  953.     /* NOTREACHED */
  954. }
  955.  
  956. struct block *
  957. gen_ecode(eaddr, q)
  958.     u_char *eaddr;
  959.     struct qual q;
  960. {
  961.     if ((q.addr == Q_HOST || q.addr == Q_DEFAULT) && q.proto == Q_LINK)
  962.         return gen_ehostop(eaddr, (int)q.dir);
  963.     else 
  964.         error("ethernet address used in non-ether expression");
  965.     /* NOTREACHED */
  966. }
  967.  
  968. void
  969. sappend(s0, s1)
  970.     struct slist *s0, *s1;
  971. {
  972.     /*
  973.      * This is definitely not the best way to do this, but the
  974.      * lists will rarely get long.
  975.      */
  976.     while (s0->next)
  977.         s0 = s0->next;
  978.     s0->next = s1;
  979. }
  980.  
  981. struct slist *
  982. xfer_to_x(a)
  983.     struct arth *a;
  984. {
  985.     struct slist *s;
  986.  
  987.     s = new_stmt(BPF_LDX|BPF_MEM);
  988.     s->s.k = a->regno;
  989.     return s;
  990. }
  991.  
  992. struct slist *
  993. xfer_to_a(a)
  994.     struct arth *a;
  995. {
  996.     struct slist *s;
  997.  
  998.     s = new_stmt(BPF_LD|BPF_MEM);
  999.     s->s.k = a->regno;
  1000.     return s;
  1001. }
  1002.  
  1003. struct arth *
  1004. gen_load(proto, index, size)
  1005.     int proto;
  1006.     struct arth *index;
  1007.     int size;
  1008. {
  1009.     struct slist *s, *tmp;
  1010.     struct block *b;
  1011.     int regno = alloc_reg();
  1012.  
  1013.     free_reg(index->regno);
  1014.     switch (size) {
  1015.  
  1016.     default:
  1017.         error("data size must be 1, 2, or 4");
  1018.  
  1019.     case 1:
  1020.         size = BPF_B;
  1021.         break;
  1022.  
  1023.     case 2:
  1024.         size = BPF_H;
  1025.         break;
  1026.  
  1027.     case 4:
  1028.         size = BPF_W;
  1029.         break;
  1030.     }
  1031.     switch (proto) {
  1032.     default:
  1033.         error("unsupported index operation");
  1034.         
  1035.     case Q_LINK:
  1036.         s = xfer_to_x(index);
  1037.         tmp = new_stmt(BPF_LD|BPF_IND|size);
  1038.         sappend(s, tmp);
  1039.         sappend(index->s, s);
  1040.         break;
  1041.  
  1042.     case Q_IP:
  1043.     case Q_ARP:
  1044.     case Q_RARP:
  1045.         /* XXX Note that we assume a fixed link link header here. */
  1046.         s = xfer_to_x(index);
  1047.         tmp = new_stmt(BPF_LD|BPF_IND|size);
  1048.         tmp->s.k = off_nl;
  1049.         sappend(s, tmp);
  1050.         sappend(index->s, s);
  1051.  
  1052.         b = gen_proto_abbrev(proto);
  1053.         if (index->b)
  1054.             gen_and(index->b, b);
  1055.         index->b = b;
  1056.         break;
  1057.  
  1058.     case Q_TCP:
  1059.     case Q_UDP:
  1060.     case Q_ICMP:
  1061.         s = new_stmt(BPF_LDX|BPF_MSH|BPF_B);
  1062.         s->s.k = off_nl;
  1063.         sappend(s, xfer_to_a(index));
  1064.         sappend(s, new_stmt(BPF_ALU|BPF_ADD|BPF_X));
  1065.         sappend(s, new_stmt(BPF_MISC|BPF_TAX));
  1066.         sappend(s, tmp = new_stmt(BPF_LD|BPF_IND|size));
  1067.         tmp->s.k = off_nl;
  1068.         sappend(index->s, s);
  1069.         
  1070.         gen_and(gen_proto_abbrev(proto), b = gen_ipfrag());
  1071.         if (index->b)
  1072.             gen_and(index->b, b);
  1073.         index->b = b;
  1074.         break;
  1075.     }
  1076.     index->regno = regno;
  1077.     s = new_stmt(BPF_ST);
  1078.     s->s.k = regno;
  1079.     sappend(index->s, s);
  1080.  
  1081.     return index;
  1082. }
  1083.  
  1084. struct block *
  1085. gen_relation(code, a0, a1, reversed)
  1086.     int code;
  1087.     struct arth *a0, *a1;
  1088.     int reversed;
  1089. {
  1090.     struct slist *s0, *s1, *s2;
  1091.     struct block *b, *tmp;
  1092.  
  1093.     s0 = xfer_to_x(a1);
  1094.     s1 = xfer_to_a(a0);
  1095.     s2 = new_stmt(BPF_ALU|BPF_SUB|BPF_X);
  1096.     b = new_block(JMP(code));
  1097.     if (reversed)
  1098.         gen_not(b);
  1099.  
  1100.     sappend(s1, s2);
  1101.     sappend(s0, s1);
  1102.     sappend(a1->s, s0);
  1103.     sappend(a0->s, a1->s);
  1104.  
  1105.     b->stmts = a0->s;
  1106.  
  1107.     free_reg(a0->regno);
  1108.     free_reg(a1->regno);
  1109.  
  1110.     /* 'and' together protocol checks */
  1111.     if (a0->b) {
  1112.         if (a1->b) {
  1113.             gen_and(a0->b, tmp = a1->b);
  1114.         }
  1115.         else
  1116.             tmp = a0->b;
  1117.     } else 
  1118.         tmp = a1->b;
  1119.  
  1120.     if (tmp)
  1121.         gen_and(tmp, b);
  1122.  
  1123.     return b;
  1124. }
  1125.  
  1126. struct arth *
  1127. gen_loadlen()
  1128. {
  1129.     int regno = alloc_reg();
  1130.     struct arth *a = (struct arth *)newchunk(sizeof(*a));
  1131.     struct slist *s;
  1132.  
  1133.     s = new_stmt(BPF_LD|BPF_LEN);
  1134.     s->next = new_stmt(BPF_ST);
  1135.     s->next->s.k = regno;
  1136.     a->s = s;
  1137.     a->regno = regno;
  1138.  
  1139.     return a;
  1140. }
  1141.  
  1142. struct arth *
  1143. gen_loadi(val)
  1144.     int val;
  1145. {
  1146.     struct arth *a;
  1147.     struct slist *s;
  1148.     int reg;
  1149.  
  1150.     a = (struct arth *)newchunk(sizeof(*a));
  1151.  
  1152.     reg = alloc_reg();
  1153.  
  1154.     s = new_stmt(BPF_LD|BPF_IMM);
  1155.     s->s.k = val;
  1156.     s->next = new_stmt(BPF_ST);
  1157.     s->next->s.k = reg;
  1158.     a->s = s;
  1159.     a->regno = reg;
  1160.  
  1161.     return a;
  1162. }
  1163.  
  1164. struct arth *
  1165. gen_neg(a)
  1166.     struct arth *a;
  1167. {
  1168.     struct slist *s;
  1169.  
  1170.     s = xfer_to_a(a);
  1171.     sappend(a->s, s);
  1172.     s = new_stmt(BPF_ALU|BPF_NEG);
  1173.     s->s.k = 0;
  1174.     sappend(a->s, s);
  1175.     s = new_stmt(BPF_ST);
  1176.     s->s.k = a->regno;
  1177.     sappend(a->s, s);
  1178.  
  1179.     return a;
  1180. }
  1181.  
  1182. struct arth *
  1183. gen_arth(code, a0, a1)
  1184.     int code;
  1185.     struct arth *a0, *a1;
  1186. {
  1187.     struct slist *s0, *s1, *s2;
  1188.  
  1189.     s0 = xfer_to_x(a1);
  1190.     s1 = xfer_to_a(a0);
  1191.     s2 = new_stmt(BPF_ALU|BPF_X|code);
  1192.  
  1193.     sappend(s1, s2);
  1194.     sappend(s0, s1);
  1195.     sappend(a1->s, s0);
  1196.     sappend(a0->s, a1->s);
  1197.     
  1198.     free_reg(a1->regno);
  1199.  
  1200.     s0 = new_stmt(BPF_ST);
  1201.     a0->regno = s0->s.k = alloc_reg();
  1202.     sappend(a0->s, s0);
  1203.  
  1204.     return a0;
  1205. }
  1206.  
  1207. /*
  1208.  * Here we handle simple allocation of the scratch registers.
  1209.  * If too many registers are alloc'd, the allocator punts.
  1210.  */
  1211. static int regused[BPF_MEMWORDS];
  1212. static int curreg;
  1213.  
  1214. /*
  1215.  * Return the next free register.
  1216.  */
  1217. static int
  1218. alloc_reg()
  1219. {
  1220.     int n = BPF_MEMWORDS;
  1221.  
  1222.     while (--n >= 0) {
  1223.         if (regused[curreg])
  1224.             curreg = (curreg + 1) % BPF_MEMWORDS;
  1225.         else {
  1226.             regused[curreg] = 1;
  1227.             return curreg;
  1228.         }
  1229.     }
  1230.     error("too many registers needed to evaluate expression");
  1231.     /* NOTREACHED */
  1232. }
  1233.  
  1234. /*
  1235.  * Return a register to the table so it can
  1236.  * be used later.
  1237.  */
  1238. static void
  1239. free_reg(n)
  1240.     int n;
  1241. {
  1242.     regused[n] = 0;
  1243. }
  1244.  
  1245. static struct block *
  1246. gen_len(jmp, n)
  1247.     int jmp;
  1248.     int n;
  1249. {
  1250.     struct slist *s;
  1251.     struct block *b;
  1252.  
  1253.     s = new_stmt(BPF_LD|BPF_LEN);
  1254.     s->next = new_stmt(BPF_SUB|BPF_IMM);
  1255.     s->next->s.k = n;
  1256.     b = new_block(JMP(jmp));
  1257.     b->stmts = s;
  1258.  
  1259.     return b;
  1260. }
  1261.  
  1262. struct block *
  1263. gen_greater(n)
  1264.     int n;
  1265. {
  1266.     return gen_len(BPF_JGE, n);
  1267. }
  1268.  
  1269. struct block *
  1270. gen_less(n)
  1271.     int n;
  1272. {
  1273.     struct block *b;
  1274.  
  1275.     b = gen_len(BPF_JGT, n);
  1276.     gen_not(b);
  1277.  
  1278.     return b;
  1279. }
  1280.  
  1281. struct block *
  1282. gen_byteop(op, idx, val)
  1283.     int op;
  1284.     int idx;
  1285.     int val;
  1286. {
  1287.     struct block *b;
  1288.     struct slist *s;
  1289.  
  1290.     switch (op) {
  1291.     default:
  1292.         abort();
  1293.  
  1294.     case '=':
  1295.         return gen_cmp((u_int)idx, BPF_B, (long)val);
  1296.         
  1297.     case '<':
  1298.         b = gen_cmp((u_int)idx, BPF_B, (long)val);
  1299.         b->s.code = JMP(BPF_JGE);
  1300.         gen_not(b);
  1301.         return b;
  1302.  
  1303.     case '>':
  1304.         b = gen_cmp((u_int)idx, BPF_B, (long)val);
  1305.         b->s.code = JMP(BPF_JGT);
  1306.         return b;
  1307.  
  1308.     case '|':
  1309.         s = new_stmt(BPF_ALU|BPF_AND|BPF_K);
  1310.         break;
  1311.  
  1312.     case '&':
  1313.         s = new_stmt(BPF_ALU|BPF_AND|BPF_K);
  1314.         break;
  1315.     }
  1316.     s->s.k = val;
  1317.     b = new_block(JMP(BPF_JEQ));
  1318.     b->stmts = s;
  1319.     gen_not(b);
  1320.  
  1321.     return b;
  1322. }
  1323.  
  1324. struct block *
  1325. gen_broadcast(proto)
  1326.     int proto;
  1327. {
  1328.     u_long hostmask;
  1329.     struct block *b0, *b1, *b2;
  1330.     static u_char ebroadcast[] = { 0xff, 0xff, 0xff, 0xff, 0xff, 0xff };
  1331.  
  1332.     switch (proto) {
  1333.  
  1334.     case Q_DEFAULT:
  1335.     case Q_LINK:
  1336.         if (linktype == DLT_EN10MB)
  1337.             return gen_ehostop(ebroadcast, Q_DST);
  1338.         error("not a broadcast link");
  1339.         break;
  1340.  
  1341.     case Q_IP:
  1342.         b0 = gen_linktype(ETHERTYPE_IP);
  1343.         hostmask = ~netmask;
  1344.         b1 = gen_mcmp(off_nl + 16, BPF_W, (long)0, hostmask);
  1345.         b2 = gen_mcmp(off_nl + 16, BPF_W, 
  1346.                   (long)(~0 & hostmask), hostmask);
  1347.         gen_or(b1, b2);
  1348.         gen_and(b0, b2);
  1349.         return b2;
  1350.     }
  1351.     error("only ether/ip broadcast filters supported");
  1352. }
  1353.  
  1354. struct block *
  1355. gen_multicast(proto)
  1356.     int proto;
  1357. {
  1358.     register struct block *b0, *b1, *b2;
  1359.     register struct slist *s;
  1360.  
  1361.     switch (proto) {
  1362.  
  1363.     case Q_DEFAULT:
  1364.     case Q_LINK:
  1365.         if (linktype != DLT_EN10MB)
  1366.             break;
  1367.  
  1368.         /* ether[0] & 1 != 0 */
  1369.         s = new_stmt(BPF_LD|BPF_B|BPF_ABS);
  1370.         s->s.k = 0;
  1371.         b0 = new_block(JMP(BPF_JSET));
  1372.         b0->s.k = 1;
  1373.         b0->stmts = s;
  1374.         return b0;
  1375.  
  1376.     case Q_IP:
  1377.         b0 = gen_linktype(ETHERTYPE_IP);
  1378.         b1 = gen_cmp(off_nl + 16, BPF_B, (long)224);
  1379.         b1->s.code = JMP(BPF_JGE);
  1380.         gen_and(b0, b1);
  1381.         return b1;
  1382.     }
  1383.     error("only ether/ip multicast filters supported");
  1384. }
  1385.